
public class SearchInRotatedSortedArray {
	public void tester() {
//		int [] a = new int [100];
//		
//		for(int i = 0 ; i < a.length ; i++) {
//			if(i <= 30) a[i] = i+70;
//			else a[i] = i-30;
//		}
//		
//		for(int i = 0 ; i < a.length ; i ++) {
//			System.out.println(i+" "+search(a, a[i]));
//		}
		
		
		int [] a = {1,2,3,4,5};
		System.out.println(searchInsert(a, 0));
		System.out.println(searchInsert(a, 1));
		System.out.println(searchInsert(a, 2));
		System.out.println(searchInsert(a, 3));
		System.out.println(searchInsert(a, 4));
		System.out.println(searchInsert(a, 5));
		System.out.println(searchInsert(a, 6));
		System.out.println(searchInsert(a, 7));
	}
	
	public int searchInsert(int[] A, int t) {
        int a = 0, b = A.length-1;
        
        while(a <= b) {
            int m = (a+b)/2;
            if(A[m] < t) a = m + 1;
            else if(A[m] > t) b = m - 1;
            else return m;
        }
        
        if(t > A[A.length-1]) return A.length;
        return a;
    }
	
	public int search(int [] A, int t) {
		int a = 0, b = A.length -1;
		
		while(a <= b) {
			int mid = (a+b)/2;
			
//			System.out.println("0: "+a+" "+b+" "+mid);
			
			if(A[0] < t) {
				if(A[mid] > t) b = mid - 1;
				else if(A[mid] < t && A[mid] >= A[0]) a = mid + 1;
				else if(A[mid] < t && A[mid] < A[0]) b = mid - 1;
				else return mid;
				
//				System.out.println("1: "+a+" "+b+" "+mid+" "+A[mid]);
			}
			else if(A[0] > t) {
				if(A[mid] < t) a = mid + 1;
				else if(A[mid] > t && A[mid] < A[0]) b = mid - 1;
				else if(A[mid] > t && A[mid] >= A[0]) a = mid + 1;
				else return mid;
				
//				System.out.println("2: "+a+" "+b+" "+mid);
			}
			else return 0;
		}
		return -1;
	}
}
